Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Solution:

  1. public class Solution {
  2.   public int search(int[] nums, int target) {
  3.     int n = nums.length;
  5.     return search(nums, 0, n - 1, target);
  6.   }
  8.   int search(int[] nums, int lo, int hi, int target) {
  9.     if (lo > hi)
  10.       return -1;
  12.     int mid = lo + (hi - lo) / 2;
  14.     if (nums[mid] == target) {
  15.       return mid;
  16.     }
  18.     if (nums[lo] <= nums[mid]) {
  19.       if (nums[lo] <= target && target < nums[mid]) {
  20.         return search(nums, lo, mid - 1, target);
  21.       } else {
  22.         return search(nums, mid + 1, hi, target);
  23.       }
  24.     } else {
  25.       if (nums[mid] < target && target <= nums[hi]) {
  26.         return search(nums, mid + 1, hi, target);
  27.       } else {
  28.         return search(nums, lo, mid - 1, target);
  29.       }
  30.     }
  31.   }
  32. }